package 题目集.贪心.huffman树;

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * https://www.acwing.com/problem/content/150
 * 合并石子，可选任意两个石子合并。每次合并有个代价，求最小代价
 */
public class ch01_合并果子 {
    /**
     * 把每个石子看作一个节点，每次合并产生一个新的节点。
     * 合并的路线会变成一棵树，原节点为这棵树的所有叶子节点。
     * 我们可以发现，每个节点的深度越深，结果加上该节点的次数越多。
     * 所以最终的结果树中，最深的节点一定是最小的。
     * 而对于两个节点产生的新节点，也同样如此。(具有最优子结构)
     * 所以我们可以用一个优先队列，每次取出两个最小的节点合并，再放回去。
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            queue.add(sc.nextInt());
        }
        long res = 0;
        while (queue.size() > 1) {
            int a = queue.poll();
            int b = queue.poll();
            queue.add(a + b);
            res += a + b;
        }
        System.out.println(res);
    }
}
